Chińczyk

Limit pamięci: 64 MB

W stolicy jest skrzyżowań oraz dróg je łączących. Sieć dróg jest taka, że z każdego skrzyżowania da się dojechać do każdego innego w dokładnie jeden sposób. Przy niektórych skrzyżowaniach znajdują się chińskie bary, zwane chińczykami.

Kozik chce zamieszkać w stolicy. W tym celu chce wybrać mieszkanie znajdujące się przy pewnym skrzyżowaniu. Położenie mieszkania musi być takie, aby odległość najdalszego chińczyka była jak najmniejsza, ponieważ Kozik lubi jeść, ale nie lubi dużo chodzić, a chciałby obejrzeć wszystkie chińczyki w mieście.

Kozik nie lubi też dużo myśleć, dlatego pomóż mu wybrać odpowiednie mieszkanie. Zakładamy, że odległość między dwoma sąsiednimi skrzyżowaniami wynosi jeden.

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą (), oznaczającą liczbę skrzyżowań. Drugi wiersz zawiera liczb całkowitych (). Jeśli jest równe 1, to oznacza, że przy -tym skrzyżowaniu znajduje się chińczyk, w przeciwnym wypadku chińczyka nie ma.

Kolejnych wierszy opisuje połączenia między skrzyżowaniami. Każdy wiersz zawiera dwie liczby całkowite i (), oznaczające, że skrzyżowania i są połączone bezpośrednią drogą. W testach wartych około punktów zachodzi dodatkowy warunek .

Wyjście

Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą, równą odległości najdalszego chińczyka dla mieszkania, które powinien wybrać Kozik. Jeżeli w mieście nie ma chińczyka, wypisz -1.

Przykład

Dla danych wejściowych:

7
0 1 0 0 1 0 1
1 3
2 3
3 4
4 5
4 6
6 7

poprawną odpowiedzią jest:

2

Autor zadania: Jacek Tomasiewicz.